#include <stdlib.h>
#include <string.h>
#include "bst.h"


// 树的初始化
int bst_init(bst_t **tree, size_t size, int (*cmp)(const void *data, const void *key))
{
    if (NULL != *tree)
        return -1;

    (*tree) = malloc(sizeof(bst_t));
    if (NULL == *tree)
        return -1;

    (*tree)->root = NULL;
    (*tree)->num = 0;
    (*tree)->size = size;
    (*tree)->cmp = cmp;

    return 0;
}

// 销毁节点及其所有子树
static void __destroy(node_t **root)
{
	if (*root == NULL)
		return ;

	__destroy(&(*root)->left);
	__destroy(&(*root)->right);

	free(*root);
	*root = NULL;
}

// 清空树
void bst_clear(bst_t *tree)
{
    __destroy(&(tree->root));
    
    tree->root = NULL;
    tree->num = 0;
}

// 销毁树并释放内存
void bst_destroy(bst_t **tree)
{
    bst_clear(*tree);

    free(*tree);
    *tree = NULL;
}

// 获取树的大小（节点数量）
size_t bst_size(const bst_t *tree)
{
    return tree->num;
}

// 插入数据
int bst_insert(bst_t *tree, const void *data)
{
    node_t *tmp = NULL;
    // 新建节点
    node_t *node = malloc(sizeof(node_t) + tree->size);
    if (NULL == node)
        return -1;

    // 给新建节点赋值
    node->left = node->right = NULL;
    memcpy(node->data, data, tree->size);

    // 将新节点插入树
    if (NULL == tree->root) {
        tree->root = node;
        tree->num++;
        return 0;
    }
    tmp = tree->root;
    while (1) {
        if ((tree->cmp)(tmp->data, data) >= 0) { // 插入到左子树
            if (NULL == tmp->left) {
                tmp->left = node;
                tree->num++;
                return 0;
            }
            tmp = tmp->left;
        } else {                                 // 插入到右子树
            if (NULL == tmp->right) {
                tmp->right = node;
                tree->num++;
                return 0;
            }
            tmp = tmp->right;
        }
    }
}

// 查找数据
void *bst_search(const bst_t *tree, const void *key)
{
    node_t *tmp = NULL;
    if (NULL == tree->root) 
        return NULL;

    tmp = tree->root;
    while (1) {
        if ((tree->cmp)(tmp->data, key) > 0) {          // 到左子树
            if (NULL == tmp->left)
                return NULL;
            tmp = tmp->left;
        } else if ((tree->cmp)(tmp->data, key) < 0) {   // 到右子树
            if (NULL == tmp->right)
                return NULL;
            tmp = tmp->right;
        } else {
            return tmp->data;                           // 找到数据
        }
    }
}

// 找到指向匹配结点的指针的地址
static node_t **__find(bst_t *tree, node_t **root, const void *key)
{
	int ret;

	if (*root == NULL)
		return NULL;

	ret = (tree->cmp)((*root)->data, key);
	
	if (ret < 0)
		return __find(tree, &(*root)->right, key);	
	else if (ret > 0)
		return __find(tree, &(*root)->left, key);
    else
		return root;
}

// 寻找数上最右侧节点
static node_t *__find_max(node_t *root)
{
	if (NULL == root)
		return NULL;

	if (NULL == root->right)
		return root;

	return __find_max(root->right);
}

// 删除节点 
static int __delete(node_t **root)
{
	node_t *del = *root;	
	node_t *r = del->right;
	node_t *l = del->left;

	if (NULL != l) {
		*root = l;
		if (NULL != r)
			__find_max(l)->right = r; // l树上最大结点的right指针指向r 
	} else {
		*root = r;
	}

	del->left = del->right = NULL;
	free(del);
	del = NULL;

	return 0;
}

// 删除数据
int bst_delete(bst_t *tree, const void *key)
{
    // 找
	node_t **del = __find(tree, &(tree->root), key);

	if (NULL == del)
		return -1;

	// 删
	__delete(del);

	return 0;    
}

static void __traval_mid(const node_t *root, void (*func)(const void *data))
{
	if (NULL == root)
		return ;
	__traval_mid(root->left, func);
	func(root->data);
	__traval_mid(root->right, func);
}

// 中序遍历
void bst_inorder(const bst_t *tree, void (*func)(const void *data))
{
    __traval_mid(tree->root, func);
}


